class Solution {
public:
    bool canMakeEqual(vector<int>& nums, int k) {
        int n = nums.size();
        int a = 0,b = 0;
        vector<int> arr(nums);
        for(int i = 0;i + 1 < n;i++){
            if(arr[i] == -1){
                a++;
                arr[i] = 0 - arr[i];
                arr[i + 1] = 0 - arr[i + 1];
            }
        }
        if(arr[n - 1] == -1){
            a = INT_MAX;
        }
        arr = nums;
        for(int i = 0;i + 1 < n;i++){
            if(arr[i] == 1){
                b++;
                arr[i] = 0 - arr[i];
                arr[i + 1] = 0 - arr[i + 1];
            }
        }      
        if(arr[n - 1] == 1){
            b = INT_MAX;
        }    
        // cout << a << ' ' << b << endl;
        return min(a,b) <= k;
    }
};
class Solution {
public:
    int countPermutations(vector<int>& com) {
        int n = com.size();
        for(int i = 1;i < n;i++){
            if(com[i] <= com[0]){
                return 0;
            }
        }
        long long ans = 1, A = 1e9 + 7;
        for(int i = n - 1;i >= 1;i--){
            ans *= i;
            ans %= A;
        }
        return ans;
    }
};
class Solution {
public:
    int countPartitions(vector<int>& nums, int k) {
        int mod = 1e9 + 7;
        int left = 0,right = 0,n = nums.size();
        vector<int> dp(n + 1);
        deque<int> max_pos,min_pos;

        vector<int> prefix_sum(n + 1, 0);
		prefix_sum[0] = 1;
        dp[0] = 1;
        for( ; right < n;right++){
            while(!max_pos.empty() && nums[right] > nums[max_pos.back()]){
                max_pos.pop_back();
            }
            while(!min_pos.empty() && nums[right] < nums[min_pos.back()]){
                min_pos.pop_back();
            }            
            max_pos.push_back(right),min_pos.push_back(right);
            while(nums[max_pos.front()] - nums[min_pos.front()] > k){
                if(left == max_pos.front())  max_pos.pop_front();
                if(left == min_pos.front())  min_pos.pop_front();
                left++;
            }
            			// Compute dp[right + 1] = sum(dp[left..right])
			dp[right + 1] =
				(prefix_sum[right] - (left > 0 ? prefix_sum[left - 1] : 0)) %
				mod;
			if (dp[right + 1] < 0) {
				dp[right + 1] += mod;
			}
			prefix_sum[right + 1] = (prefix_sum[right] + dp[right + 1]) % mod;
        }
        for(int i = 0;i <= n;i++){
            cout << dp[i] << ' ' << prefix_sum[i] << endl;
        }
        return dp[n] % mod;
    }
};